import java.util.ArrayList;
import java.util.List;

public class Solution17 {
    public List<String> letterCombinations(String digits) {
        if (digits.length()==0){
            return new ArrayList<>();
        }
        List<String> list=new ArrayList<>();
        char[] chars=new char[digits.length()];
        String[] strings=new String[]{"","","abc","edf","ghi","jkl","mno","pqrs","tuv","wxyz"};
        dfs(0,strings,digits,chars,list);
        return list;
    }

    private void dfs(int k, String[] strings, String digits, char[] chars, List<String> list) {
        if (k==digits.length()){
            list.add(String.valueOf(chars));
            return;
        }
        for (char c : strings[digits.charAt(k) - '0'].toCharArray()) {
            chars[k]=c;
            dfs(k+1,strings,digits,chars,list);
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution17().letterCombinations("23"));
    }
}
